/*
  二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
  这道题我们考虑使用递归来做
  思考：
      1. 每个节点需要做什么
      2. 之后如何递归
      3. 递归退出条件
    每个节点如果传递进来，都需要判断它们的大小关系，也就是 root.left.val < root.val < root.right.val
    如果符合条件那么继续将左子树和右子树传递
    如果左子树和右子树为空，则返回true
  第二种思路：
    中序遍历的结果一定是从小到大排列的，我们只需要得到中序遍历的结果
    之后再判断是否从小到大排列的，返回结果即可
*/
const isValidBST = function (root) {
  // if (!root) return true
  // if (root.left.val <= root.val <= root.right.val) {
  //   return isValidBST(root.left) && isValidBST(root.right)
  // } else {
  //   return false
  // }
  const result = []
  const dfs = (root) => {
    if (!root) return
    dfs(root.left)
    result.push(root.val)
    dfs(root.right)
  }
  dfs(root)
  for (let i = 0; i < result.length - 1; i++) {
    if (result[i] <= result[i + 1]) continue
    else return false
  }
  return true
}
// 方法二：
const isValidBST2 = function (root) {
  const fun = (root, left, right) => {
    if (root == null) return true
    if (root.val <= left || root.val >= right) return false
    return fun(root.left, left, root.val) && fun(root.right, root.val, right)
  }
  return fun(root, -Infinity, Infinity)
}
